package com.xzz.bfs;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author: hhz
 * @create: 2022-04-19 10:56
 * 821. 字符的最短距离
 **/
public class ShortestToChar {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(shortestToChar("loveleetcode", 'e')));
    }

    public static int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                deque.addLast(i);
                ans[i] = 0;
            }
        }
        int[] dirs = new int[]{-1, 1};
        while (!deque.isEmpty()) {
            int t = deque.pollFirst();
            for (int dir : dirs) {
                int ne = t + dir;
                if(ne>=0 && ne<n && ans[ne]==-1){
                    ans[ne]=ans[t]+1;
                    deque.addLast(ne);
                }
            }
        }
        return ans;
    }
}
